package leetcode_500;

/**
 * KthSmallestInLexicographicalOrder_440_给定一个整数 n和位数k 寻找小于等于n的字典顺序的第k个数
 * 2018年8月18日 下午2:09:49
 * @author 周杨
 * describe :用前缀法  AC 8%
 * see:https://www.cnblogs.com/charlesblc/p/5993594.html
 */
public class KthSmallestInLexicographicalOrder_440_ {
	private int getCount(int n, long prefix) {
        if (prefix == 0) {
            return 0;
        }

        int count = 0;
        int step = 1;
        while ((prefix+1) * step <= n+1) {
            count += step;
            step *= 10;
        }
        if (prefix * step <= n) {
            count += n + 1 - prefix * step;
        }
        return count;
    }

    public int findKthNumber(int n, int k) {

        int prefix = 0;

        while (k > 0) {
            if (prefix != 0) {
                if (k == 1) {
                    return prefix;
                }
                else {
                    k--;
                }
            }

            for (int i=0; i<10; i++) {

                int count = getCount(n, prefix*10+i);
                if (k > count) {
                    k -= count;
                }
                else {
                    prefix = prefix * 10 + i;
                    break;
                }
            }
        }
        return prefix;
    }
}
